Total relation

 ( Properties Of Binary Relations ) 

In mathematics, a binary relation R ⊆ X× Y between two sets X and Y is total (or left total) if the source set X equals the domain { x : there is a y with xRy }. Conversely, R is called right total if Y equals the range { y : there is an x with xRy }.

When f: X → Y is a function, the domain of f is all of X, hence f is a total relation. On the other hand, if f is a partial function, then the domain may be a proper subset of X, in which case f is not a total relation.

"A binary relation is said to be total with respect to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else." Functions from Carnegie Mellon University

---

Algebraic characterization Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let $X,Y$ be two sets, and let $R\backslash subseteq\; X\backslash times\; Y.$ For any two sets $A,B,$ let $L\_\{A,B\}=A\backslash times\; B$ be the universal relation between $A$ and $B,$ and let $I\_A=\backslash \{(a,a):a\backslash in\; A\backslash \}$ be the identity relation on $A.$ We use the notation $R^\backslash top$ for the converse relation of $R.$

• $R$ is total iff for any set $W$ and any $S\backslash subseteq\; W\backslash times\; X,$ $S\backslash ne\backslash emptyset$ implies $SR\backslash ne\backslash emptyset.$
  (2012). 9783642779688, Springer Science & Business Media. ISBN 9783642779688
• $R$ is total iff $I\_X\backslash subseteq\; RR^\backslash top.$
• If $R$ is total, then $L\_\{X,Y\}=RL\_\{Y,Y\}.$ The converse is true if $Y\backslash ne\backslash emptyset.$If $Y=\backslash emptyset\backslash ne\; X,$ then $R$ will be not total.
• If $R$ is total, then $\backslash overline\{RL\_\{Y,Y\}\}=\backslash emptyset.$ The converse is true if $Y\backslash ne\backslash emptyset.$Observe $\backslash overline\{RL\_\{Y,Y\}\}=\backslash emptyset\backslash Leftrightarrow\; RL\_\{Y,Y\}=L\_\{X,Y\},$ and apply the previous bullet.
• If $R$ is total, then $\backslash overline\; R\backslash subseteq\; R\backslash overline\{I\_Y\}.$ The converse is true if $Y\backslash ne\backslash emptyset.$
  Gunther Schmidt (2026). 9780511778810, Cambridge University Press. ISBN 9780511778810
  Definition 5.8, page 57.
• More generally, if $R$ is total, then for any set $Z$ and any $S\backslash subseteq\; Y\backslash times\; Z,$ $\backslash overline\{RS\}\backslash subseteq\; R\backslash overline\; S.$ The converse is true if $Y\backslash ne\backslash emptyset.$Take $Z=Y,S=I\_Y$ and appeal to the previous bullet.

---

See also

• Serial relation — a total homogeneous relation

---

Notes

• Gunther Schmidt & Michael Winter (2018) Relational Topology
• C. Brink, W. Kahl, and G. Schmidt (1997) Relational Methods in Computer Science, Advances in Computer Science, page 5,
• Gunther Schmidt & Thomas Strohlein (2012)1987
• Gunther Schmidt (2011)

Post Comment